package fun.coding.leetcode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class WordLadder {

	public static void main(String[] args) {
		WordLadder wl = new WordLadder();
		
		String[] dictionary = {"hot","dot","dog","lot","log"};
		String[] dictionary2 = {"hot","cog","dot","dog","hit","lot","log"};
		Set<String> dict = new HashSet<String>(Arrays.asList(dictionary));
		Set<String> dict2 = new HashSet<String>(Arrays.asList(dictionary2));
		// "hit" -> "hot" -> "dot" -> "dog" -> "cog" -> 5
		System.out.println(wl.ladderLength("hit", "cog", dict));
		System.out.println(wl.ladderLength("hit", "cog", dict2));
	}

	public int ladderLength(String start, String end, Set<String> dict) {
		if (start == null || end == null || dict == null || dict.size() == 0) return 0;	
		
		// if same, no need to transform
		if (start == end) return 0;
		
		Queue<String> q = new LinkedList<String>();
		// There will be many dups, use a set to keep track of
		Set<String> processedSet = new HashSet<String>();
		
		q.offer(start);
		int length = 1;
		
		while (!q.isEmpty()) {
			// BSF each level use this count to know which level we are in
			int count = q.size();
			while (count > 0) {
				String cur = q.poll();
				for (int  i = 0; i < cur.length(); i++) {
					char curChar = cur.charAt(i);
					
					// For each char, do a bsf, this guarantees it is the shortest
					for (char c = 'a'; c <= 'z'; c++) {
						if (curChar == c) continue;
						
						StringBuilder sb = new StringBuilder(cur);
						sb.setCharAt(i, c);
						String newStr = sb.toString();
						
						// Note here compare by value, not == (reference)
						if (newStr.equals(end)) {
							return length + 1;
						}
						
						if (dict.contains(newStr) && !processedSet.contains(newStr)) {
							q.offer(newStr);
							processedSet.add(newStr);
						}
					}
				}
				count--;
			}
			length++;
		}
		// There is no path
		return 0;
	}
}
